perm filename BEESON.KNO[S85,JMC] blob
sn#794309 filedate 1985-05-27 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00003 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 ∂12-May-85 1649 ucscc!beeson%ucscd.ucscc.UUCP@Berkeley the paper I promised you
C00131 00003 Date: 23 May 85 1059 PDT
C00140 ENDMK
C⊗;
∂12-May-85 1649 ucscc!beeson%ucscd.ucscc.UUCP@Berkeley the paper I promised you
Received: from UCB-VAX.ARPA by SU-AI.ARPA with TCP; 12 May 85 16:48:10 PDT
Received: by UCB-VAX.ARPA (4.24/4.46)
id AA21747; Sun, 12 May 85 16:44:55 pdt
Received: from ucscd.UCSC (ucscd.ARPA) by ucscc.UCSC (4.12/4.7)
id AA17847; Sun, 12 May 85 14:08:53 pdt
Received: by ucscd.UCSC (4.12/4.7)
id AA24610; Sun, 12 May 85 14:06:20 pdt
Date: Sun, 12 May 85 14:06:20 pdt
From: ucscc!beeson%ucscd.ucscc.UUCP@Berkeley (20012000)
Message-Id: <8505122106.AA24610@ucscd.UCSC>
To: su-ai.jmc@Berkeley
Subject: the paper I promised you
Cc: clt%ucbvax!su-ai.ucscc.UUCP@Berkeley
Logic and Knowledge
Michael Beeson
ucbvax\!ucscc:beeson
First Draft.
Not for Circulation.
For private criticism.
Warning: No list of references.
Incomplete references to literature.
Half-baked ideas.
Although formalized theories have been
devised to express the most important
fields of mathematics and some progress
has been made in formalizing certain
empirical sciences, there is at present
no formal theory in which one can express
the kind of means-end analysis used in
ordinary life.
-McCarthy [1963]
Introduction
Although it is twenty years old, the quotation above is still true.
Nor do we imagine that the formalism presented here is completely
adequate for ``everyday life''. Nevertheless, we think it is a
step in that direction. Our formalism permits a useful organization
of knowledge, and provides for its use in automatically controlled
nested hierarchies of planning and action, with the ability to recognize
when something has not gone according to plan, and with some ability
to recover from such setbacks.
McCarthy and others have always maintained that logic was adequate for
the representation of knowledge. The language PROLOG lends some support
to this thesis, but experience in expert system design points to the
necessity of more sophisticated control structures; too many unstructured
rules are unmanageable. Minsky and his school have argued in favor
of frames and scripts because of their efficiency in helping the system
find just the right chain of reasoning among many possible chains. This
is characteristic of an effective control structure; frames and scripts
should be viewed as control structures, not as data structures.
This view has led us to look for the eventual unification of the
scripts-and-frames approach to knowledge representation with the
first-order-logic approach (and the subsumption of both) via
the construction of a more elaborate system, based on logic,
but with attention focussed on the {\it control structure}.
If logic is to be useful for knowledge representation, a control
structure must be specified. To put the matter otherwise, we must
give not only a declarative semantics, but also a procedural semantics.
This distinction between a logic as a set of rules and a logic as
rules plus an algorithm for applying them is familiar to workers in
automated deduction, but has yet to flower in the field of
knowledge representation. PROLOG has broken ground in this direction,
but it uses only the most primitive backtracking as a control structure.
While this has been useful for many purposes, for artificial intelligence
we should really develop a much more sophisticated control structure.
In this paper we propose a control structure, to which
we give the name ``situations''. As in the case of frames and scripts,
at first glance a situation may appear to be a data structure, that is,
a framework in which one can record facts about the environment, the
other agents to be found there, and what one can do in this situation.
We shall show, however, that if this is done properly, it is not only
possible but quite natural to use situations as a control structure
to control the ``firing'' of the rules which govern applicable actions
or deductions in that situation.
\footnote\dag{Barwise and Perry have used the word ``situation'' in their
studies of the semantics of natural language. Our use of the word is
different. Roughly speaking, one of their situations records only the
facts of the situations, and not the information about what one can
or should do when in that situation; our ``situations'' also include
the rules governing action in that situation. McCarthy [1963] also
used the word as Barwise and Perry do, to reflect the facts but not
the potential actions.}
In the first few sections of the paper, we shall develop
some preliminaries. In the middle of the paper we introduce our concept
of situation, giving several examples as we unfold the various features
of the definition. There we concentrate on the adequacy of our
definition of situation as a data structure. Only in the last
part of the paper do we return to the theme of situations as control
structures, which is what we believe makes the definition fruitful.
1. Default reasoning and the form of rules
Most current expert systems implement a system of rules of the form,
if <conditions> then <conclusion>
The language PROLOG is explicitly designed to permit statements of this form.
One difficulty with PROLOG-type systems for use in artificial intelligence
is that the number of rules needed to deal with a simple situation
may be unreasonably large if all unusual variants of the situation are
to be taken into account. We shall not reiterate the many examples
which have been put forward to illustrate the need for rules of the form
If <conditions> then <conclusion> unless <contraindications>
Rules of this form could always be converted into the logical form of
PROLOG rules by adding the negation of each of the ``contraindications''
to the list of ``conditions'', so in some theoretical sense no new power
is added by considering ``unless'' clauses. Specifically, in the sense of
declarative semantics no new power is added. This observation is not
relevant to our approach, because we intend to use the form of rules in
defining a procedural semantics for a system involving rules of the specified
form. The intuition behind this use of the form of rules is that in certain
circumstances one should not {\it examine} the list of contraindications,
but use only the {\bf if-then} part of the rule. To take the usual example:
if it's a bird
then it can fly
unless C1, C2,...
We may find it expedient to ignore C1, C2,... until we find a bird
that apparently can't fly. This is known as ``default reasoning''.
We assume (by default) that the contraindications do not apply unless
and until ``something has gone wrong''. One question which we think
has not been sufficiently addressed in the literature is {\it when}
default reasoning should be used. To give an example: one may assume by
default that a car which starts is ready to be driven. One is likely to
make this assumption when one is about to make a short trip to the grocery
store. If, however, one is starting out on a long vacation trip tomorrow,
one will not ignore the ``unless'' clauses, but check the car out thoroughly
to determine whether it is actually fit to drive. The point of the example
is that it is the {\it situation} that determines the kind of reasoning
which should applied.
2. Default reasoning at the control level
Consider the following attempt to describe the control of a system of
rules of the form {\bf if-then-unless}.
if one of the if-conditions in the list is satisfied (after unification)
then apply that rule without regard to the contraindications
unless something goes wrong when you do.
This makes it evident that what is needed is some more precise way of
specifying what it means that something has gone wrong.
Reflection shows that ``something has gone wrong'' means
``something has gone contrary to expectations''. One relatively
crude way of interpreting that would be that a contradiction is reached,
e.g. a bird that cannot fly. We shall interpret ``something has gone
wrong'' as ``something has not gone according to plan''.
A ``plan'' might be as simple as an ``expectation'', or it might be
quite detailed. In everyday life, we always have a ``plan'' in mind.
The concept of ``plan'' is discussed in detail later on in the paper;
we bring it up now only to make the following central point:
{\it it may be possible to specify a
control structure for if-then-unless rules which makes use of the
fact that they are written in if-then-unless form, instead of in a
logically equivalent if-then form.}
3. If-then-except Rules
Our formalism for situations does not use if-then-unless rules,
but rather a generalization of this form of rule to which we were led
by the consideration of examples. The kind of rule which commonly
arises is,
if A then B unless C; and in that case, D.
In other words, often we do not merely wish to specify the
exceptional cases to which the main rule does not apply, but
we wish to give a subsidiary rule which does apply in the
exceptional cases. It seems to be a fruitful construction
to allow these subsidiary rules to also contain exceptions and
further subsidiary rules. We use the word ``except'' in this
construction. Formally we make the following definition.
Definition: A rule is an expression of the form
if A then B except C, where A is a list of literals,
B is a list of rules, and C is a list of rules.
Thus ``if A then B unless C; and in that case D'' can be
written ``if A then B except (if C then D)''. But more generally
the ``if C then D'' part might itself have exceptions. The special
case ``if A then B unless C'' (in which it is not specified what to
do in case C) can be rendered, ``if A then B except (if C then fail)''.
Note that formally speaking, a rule is just a triple of a certain
kind; the words {\bf if}, {\bf then}, and {\bf except} just
serve as markers to separate the parts of the triple.
We think that this definition of rule corresponds well
to the way in which people write rules in natural language, as
well as being a tool in the formalism to be developed in this paper.
When we actually write out such rules, we will use indentation
as a typographic aid to separating the parts of a rule. We will
justify the left margins of the if, then, and except at a given
level, and indent the subsidiary rules, in a style which will be
made clear by example.
Our first aim is to illustrate the definition by giving
an example of a rule with nested exceptions. The example is
taken from a Red Cross first aid manual. It consists of
some of the rules for dealing with a poisoning case:
if the victim has swallowed poison;
the poison was not a strong acid, alkali, or a petroleum product;
then if you have the original container of poison;
then read the label;
if a specific antidote is mentioned;
then give that antidote;
except if you can't obtain it quickly enough
then proceed as if you did not have the container;
if you don't have the original container of poison
then dilute the poison by giving water or milk;
induce vomiting;
get medical help immediately.
if the poison was tranquilizers, barbituates, paregoric, alcohol,
or a drug containing opium;
then give the victim coffee or strong tea;
except if the victim is unconscious
then keep his airway open;
if the victim is not breathing
then give artificial respiration;
do not give fluids;
transport the victim as quickly as possible to get medical help;
if transporting the victim to medical help;
then take along the poison container
except if you don't have the container;
then take along a sample of vomit instead.
These rules have been taken almost literally from the Red Cross manual.
There are some interesting things to notice about these rules.
(1) The rules leave a good deal to common sense. For example,
if you can't get the specific antidote prescribed on the container
then you should use the other rules instead; I spelled that out
explicitly. Similarly, it is left to common sense that if you
don't have coffee or tea, then you should not hold up all other
operations while you go to the store for coffee; and if you are
taking the victim to the hospital but have neither poison container
nor vomit sample that you shouldn't just stand there wondering how
to follow the rules, you should go to the hospital anyway.
\footnote\dag{The problem of formalizing common sense has received a good
deal of attention. The problem has two parts: (1) how to express the
vast amount of common-sense knowledge in a precise form, and (2) once
a formalism is at hand, how to avoid being overwhelmed by the
myriad of possible variations that must be dealt with.
We hope that the form of rules discussed here is a contribution to (1),
and the procedural semantics discussed below is a contribution to (2),
but neither will be explicitly discussed in this paper.}
(2) The Red Cross manual makes use of a form of indentation notation,
though not as formal as the one I have used above. It does, however,
repeat some "except" clauses in a logically superfluous way at subsidiary
levels. This redundancy is no doubt wise; one can't count on a person
faced with a poison victim to have computer-like precision in executing
nested rules.
Note that the definition of rule allows both the "then part" and the
"except part" to be lists of rules. For many applications it would
suffice to require the "then part" to be a list of clauses, only
allowing the "except part" to be rules. But the above example
shows that it is quite natural to allow the more general form.
We shall give one more example of a rule. This is a rule for
entering a building open to the public, such as a restaurant.
if you are outside a building, say B;
you want to be inside B;
then locate a door, say y, in B;
go through door y;
except if y is locked;
then look inside;
see people or signs of activity;
look for another door;
if another door is found, say z;
then go through door z;
This somewhat primitive rule will result in giving up if the second door
is also locked.
4. Knowing How versus Knowing that, or, Propositions and Actions
Compare the following two rules:
if you are outside building x and y is a door in x
you want to be inside x
then you go through y
if you are outside building x and y is a door in x
you go through y
then you are inside x
One obvious difference is that the first rule doesn't guarantee us
that going through the door will bring us inside x. We might,
for example, find ourselves in the courtyard. Let us neglect that
difference for the moment, in order to call attention to another
difference. The first rule represents ``knowing how'' to get inside
a building. The second rule represents ``knowing that'' the result
of going through doors is to get inside. The two rules are
epistemologically dissimilar, since they embody different kinds of
knowledge.
The distinction between knowing how and knowing that is reflected in
the technical distinction between procedural and declarative representation
of knowledge. The question, whether (or to what extent) this distinction
is real or artificial has been argued both in philosophy and computer
science. For example, ML83 argues that knowing that a
proposition A is true is the same as knowing how to verify A.
The language PROLOG is based on a blurring of the distinction,
treating both actions and propositions as terms. If PROLOG ``solves''
the predicate P(x), that solution may cause effects, such as
input or output or modification of the program itself. This leads us
to propose the (informal) definition:
A {\it proposition} is an atomic formula such that an attempt to verify
(an instance of) it does not change the state of affairs. An {\it action}
is an atomic formula such that attempts to ``verify'' it do change
the state of affairs. This definition is informal. For the purposes of
this paper, we use the words in a different sense: the programmer must
declare (type) each literal introduced as either a proposition or
an action. It is assumed that, unless otherwise specified, the
programmer will do this in a natural way in accordance with the
informal definition.
\footnote\dag{One of the cornerstones of quantum physics is that
there are no propositions in the sense defined here. If we try to
solve position(x), we will change the state of affairs with regard to
momentum(x). However, this is irrelevant to the events on the human scale
which we are trying to formalize.}
To illustrate what we mean, let us consider a standard PROLOG solution
to the problem of going through a door.
inside(X):-building(X),outside(X),door(X,Y),go←through(Y).
Here we assume that go←through is a procedure defined something
like this:
go←through(X,Y):-retract(outside(X)),assert(inside(X)).
This would be a crude version of go←through; a more elaborate simulation
of reality would include subprocedures for finding the doorknob, turning it,
stepping through, etc. The main point is that go←through is an
action, since it modifies the data base of facts.
{\footnote\dag Not only does it modify the list of facts known about
the world, it modifies it in a way corresponding to a change in the
facts themselves, as opposed to our knowledge of the facts.}
This program corresponds to the second rule given above. Were we to
try to write the first rule in PROLOG, it might come out like this:
go←through(X,Y):-building(X),outside(X),active←goal(inside(X)),door(X,Y),
Here active←goal(inside(X)) corresponds to "if you want to be inside X".
This rule doesn't work in PROLOG, which always chains backwards from
the goal; the first version is correct in PROLOG.
Suppose we are outside Luigi's restaurant. Can PROLOG find a plan to get us
inside Luigi's? No. For although we have outside(Luigi's), building(Luigi's),
the query
?-inside(Luigi's).
causes PROLOG to answer ``no'', because PROLOG does not know that by
executing go←through it could achieve inside(Luigi's), viz.
?-go←through(Luigi's,y),inside(Luigi's).
y=front←door, yes
PROLOG is in the position of a stupid robot who
knows {\it how} to go through doors but does not know {\it that}
going through doors has the effect of making you inside when you were outside!
In order to improve the situation, we have to give PROLOG this knowledge
explicitly:
inside(x):-outside(x),door(x,y),go←through(x,y).
After this clause is added, then PROLOG can succeed in getting us into
Luigi's.
This example illustrates an important principle: knowing how to do
something is not the same as knowing what its effects are. It is the
latter that is important in planning. Note that both cases are possible:
one may know how to do something without knowing what its effects are
(an all-too-common situation!), or one may know the effects of an action
without knowing how to do it; e.g. babies learn what the effect of
going through doors is long before they are able to reach the doorknob.
Our system of requiring literals to be typed as actions or propositions
carries with it the additional principles:
(1) if A is a proposition, then solve(A) is an action.
The action solve(A) is performed as in PROLOG, by applying the most
general unifier to the variables in A (if any) which permit the deduction
of the resulting instance of A from facts in the current database and
rules in the current list of axioms. The execution of solve(A) will
be successful if and only if such a deduction can be found.
(2) if A is an action, then can(x,A) is a proposition.
The meaning of the proposition can(x,A) is that agent is able to
perform action A. We write can(A) for can(I,A), where ``I'' is the
``principal agent'', i.e. the one doing the thinking. Can(A) is
similar to the modal operator of possibility, except that it applies
not to propositions but to actions.
When we write an action in the then-part of a rule, we intend it
to carry the modal force of necessity. That is, in that syntactic
location, A should be read as must(A). We do not need to introduce
``must'' explicitly. When an action A occurs in the if-part of a
rule, on the other hand, it carries no modal force at all. Such
occurrences are used to express knowledge about the results of actions;
they mean simply, ``if the action A is performed, then...''
This is not intended to be an exhaustive list of the relations between
propositions and actions; for example, we shall want versions of
assert and retract as in PROLOG. Note that assert and retract
have effects only on the program's database, i.e. on its knowledge
of the state of affairs, not on the actual state of affairs (except
insofar as the database is part of the state of affairs).
5. Actions, agents, and active goals
The only action that PROLOG can take that affects the outside world
is ``write''. On the other hand, the only action represented in
PROLOG which can be taken by an agent other than the principal
agent is ``read''. This is in a sense a joint action by PROLOG and
an outside agent, since it can only take place when it has been called
for by PROLOG.
In fact, this is a general feature of all AI programs so far, at least
as far as the author knows. For example, a chess program allows the
opponent as an agent, but she may move only when the program calls for
her to do so. In real life, on the other hand, we are constantly subject
to the actions of other agents, which are not under our control.
A truly intelligent machine must also be able to function in an environment
in which other agents may act at will.
So far as the author knows, no AI program has yet seriously concerned
itself with the goals of another agent. Chess-playing programs, for
example, do not attempt to model the reasoning processes of their
opponent, unlike human chess players. PROLOG, of course, is designed
around the goal structure of the principal agent, as are many special-
purpose AI programs. Hence in PROLOG, it is not necessary to make
the predicate active←goal explicit, as we have done in several examples
of rules given above. In general, however, we will have to formalize
the concept of active←goal of an agent. As with ``can'', if the agent
is not mentioned, it is presumed to be the principal agent.
In general, rules will be fired (causing actions to be performed) only
if some active goal has (directly or indirectly) caused the firing.
There is an interesting exception to this generalization: there are
certain rules of the form ``if A then B'', in which A is a list of
propositions not mentioning any active goal. Such a rule represents
a compulsory action, which must be executed regardless of one's aims.
In other words, a natural law. For example,
if object(x);
not←supported(x);
then falls(x).
The author does not know a direct way to simulate such a natural law in
PROLOG. For example, if we add to a simple blocks-world simulation
an action remove(x), which causes block x to disappear suddenly,
how will we make the blocks which were on top of x fall to the table
or to whatever previously supported x? We will have to add
clauses to the definition of remove, so that when remove is executed
the previously supported blocks will fall. But this is unrealistic;
it is not removing a block which causes the blocks above to fall,
it is the law of gravity. Instead there should be a demon in the
control structure which constantly watches for unsupported objects
and makes them fall. This is similar to the case of actions undertaken
by an outside agent; indeed if we are theistically minded, we will
ascribe such actions to active goals of a divine agent, although for
our purposes, as Laplace said to Napoleon, ``I had no need of that
hypothesis''.
Another feature of PROLOG which (though it can be useful in the hands
of a skilled programmer) is not very natural for use in AI, is that
PROLOG may perform actions during execution which are irreversible.
If the search is not fruitful and backtracking passes that action,
it cannot be undone. Here is an example:
not←dangerous←animal(x):- animal(x), stick←head←in←mouth(x), survive.
not←dangerous←animal(x):-lamb(x).
animal(lion).
animal(lamb).
stick←head←in←mouth(lion):-halt.
Ask this PROLOG program to find a not←dangerous←animal. But don't try
to use it in real life!
The moral of the example is that intelligence demands thought in
``subjunctive mode''. We must be able to perform ``gedanken
experiments'' in which we {\it suppose} certain actions to be
performed, try to predict the results, and use the prediction
together with reasoning to form a plan. For example, there is no
reason why one could not insert a ``subjunctive switch'' into the
PROLOG interpreter, such that in subjunctive mode, the effects of
assert and retract would be undone if these commands were backtracked
over. The difficulty would come with ``read'' and ``write'', which
interact with the outside world. You cannot take back actual actions
in general, although some may be reversible. Even taking a move back
in friendly chess does not undo all the effects of the move, as you can
verify by trying to take back several in a row.
Thinking in the subjunctive mode is clearly closely related to the
kinds of thought processes necessary to model the thinking of other
agents in the environment. Subjunctive mode amounts to a mental model
of your own (potential) thought and action; if you can model your own
processes, why not someone else's? Such modelling is, in my
opinion, an absolute prerequisite to intelligence.
6. Firing If-then Rules
A rule of the form if A then B, in which B is a list of actions
and A a list of propositions, is called a production rule. If we
drop the restrictions about actions and propositions and allow
A and B to be any positive literals, we have a ``simple if-then rule''.
An if-then rule, or for emphasis a nested if-then rule, is
an if-then-except rule without any except-parts; that is,
a simple if-then rule is an if-then rule, and if A is
list of positive literals, and B is a list of nested if-then rules, then
(if A then B) is a nested if-then rule. Similarly we may speak of
nested production rules: a production rule is a nested production rule,
and if A is a list of propositions, and B is a list of nested production
rules, then (if A then B) is a nested production rule.
For example, a rule of the form
if A;
then if B then C;
if D then E;
is a nested production rule, if A,B, and D are propositions and C,E are
actions. We now raise the question whether this rule should be regarded as
equivalent to the two production rules
if A,B then C;
if A,D then E.
We argue that the answer should be ``no'', since performing action
C may make A false, which in the first rule will not block the firing
of ``if D then E'', but in the second example will. Note that traditional
model theory provides a declarative semantics only for rules not including
actions, so we are appealing here only to an intuitive semantics of such
rules, preparatory to defining a formal procedural semantics.
We see no obvious way in which nested production rules can be reduced to
equivalent production rules; it seems to be a genuinely larger class of rules.
We now define what it means to fire a nested if-then rule.
We have in mind primarily nested production rules, although the
definition we give applies formally to the larger class of nested
if-then rules. We write the definition as a pidgin PROLOG program:
call←list([A|L]):-call(A),call←list(L).
call←list([]).
/*call←list calls all the literals in the list L*/
fire([B|L]):-fire(B),fire(L).
fire([]).
/*to fire a list of rules, fire every rule in the list*/
fire(if A then B):-call←list(A),fire(B).
fire(X):-proposition(X),assert(X).
fire(X):-call(X).
*/call(X) is PROLOG's way of saying, do the action X*/
*/Note that fire(if A then B) will fail unless A can be verified)*/
7. Firing If-Then-Except Rules
We first define the notion of the ``default version'' of an
if-then-except rule. Loosely speaking, the default version R sub D
of a rule R is obtained by dropping all the except-parts (at all levels),
so that an if-then rule (nested production rule) is obtained.
More precisely: R sub D is defined by the following clauses:
(i) if R is an if-then rule then R sub D is R.
(ii) (if A then B except C) sub D is (if A then (B sub D)).
(iii) [C|L] sub D is [C sub D |L sub D].
(iv) [] sub D is [].
We next define what it means to fire an if-then-except rule.
The following pidgin PROLOG program extends the one in the
previous section which defines fire(A) for an if-then rule A or
list of such rules. (The program is pidgin because it uses the
notation ``if A then B except C'' instead of prefix notation for
a binary operator f(A,B,C).)
fire(if A then B except C):-fire (if A then (B sub D)).
/*first try to fire the default version*/
fire(if A then B except [C|L]):-fire(if A then B except C).
fire(if A then B except [C|L]):-fire(if A then B except L).
fire(if A then B except C:-fire(C).
/*if firing the default version fails, then check the except-if
clauses at the first level. If one of them, say C, holds, then fire the
rule of which C is the if-part.*/
For example, consider the rule given above about getting into a building
by going through a door; the except-part concerned what to do in case
the door is locked. Suppose we fire this rule while standing in front
of the front door of Luigi's restaurant. Suppose the procedure
go←through(Luigi's, frontdoor) fails. Then the definition of firing
the rule calls for us to check whether the door is locked. Suppose
it does turn out to be locked. Then we have to follow the instructions
given in the except-then part of the rule, that is, we look for people
or signs of activity in Luigi's. If we do not find them, we fail in our
attempt to fire this rule, for there are no more except-parts to check.
If we do see people or signs of activity, then we use locate←door to
find another door, and try go←through again on that door. (This example
will be worked out in formal detail in another section.)
Now that we have defined firing rules, we can state another connection
between actions and propositions:
if R is a rule, then fire(R) is an action.
This law generates actions which can be used again to form new rules.
8. Situations
Our thesis is that rules as discussed above are always applied in the
context set by some {\it situation}.
We shall give a formal definition of "situation", which may appear
rather abstract. Through the consideration of a number of examples
we will show that the formalism works in a useful way.
Definition: A situation is a quadruple S=(E,R,G,Y), where
(1) E is a list of clauses, called the entry conditions of S.
(2) R is a list of rules, called the rules of S. (Here we mean
if-then-except rules as defined above.)
(3) G is a list of clauses, called the goals of S.
(4) Y is a list of situations, called the subsituations of S.
Note that the definition is inductive, since something is seen to
be a situation only after its subsituations have been seen to be
situations. The basis of the inductive definition is the case in
which Y is the empty list. Such a situation is called ``atomic''.
An element which one feels intuitively should be represented in a
situation is the agents involved. Every situation implicitly involves
at least one agent, the ``I'' or principal agent who is doing the
thinking. In our formalism, other agents will be represented by
predicates representing their roles. The particular entities playing
those roles at the moment will be established by unification when
entering the situation. For example, in a certain situation in a
restaurant one expects a waiter to be involved. There would be
a predicate waiter(x); that situation could not be entered until
one had solved waiter(x), identifying a particular person as the waiter.
Consider for instance the situation of playing chess. According to
our formalism, White is in one situation, Black is in a different
situation. An alternative way of using the word would be to say that
both are in the same situation, but in different roles. We shall not
use the words in that way. (This will be important later on in
the problem of forming ``models of other minds''. We have to mentally
simulate the other agent's situation in order to predict her behavior.)
9. Scripts as situations
When specific situations are written out, we abandon the formal quadruple
notation and specify directly the name of the situation, the
entry conditions, goals, rules, and subsituations.
For purposes of illustration we shall often refrain from formalizing
the language sufficiently to express everything in clauses as would
officially be required; this is a simple exercise.
Our purpose in this section is to give an example of a situation
which will illustrate the concept. We have chosen an example which
will, at the same time, illustrate how a script can be formalized
as a situation.
The restaurant situation
entry conditions: restaurant(x), at←hand(x).
to enter this situation you must be outside a restaurant.
That is, the variable x has to be unified with the name of a particular
restaurant and the two clauses listed must then be satisfied.
goals: eat y in restaurant x, leave restaurant x.
An interesting feature here is that the variable y might be unified with
``dinner'' sometimes and with ``breakfast'' at other times. This will be
taken care of by the rules of the situation, which may include for
example ``if it's after five pm then y=dinner''.
subsituations: entering restaurant, getting seated, deciding what to
order, ordering, waiting for the food, eating the food,
after eating, paying, leaving the restaurant.
rules: the list of rules in this situation is empty. :
This situation is an example of a {\it script}. We define a script
to be a situation in which, if all goes well, we simply pass through
the subsituations in the order they are given. That is, a script is
like a program. By contrast, the situation of playing chess is not
a script; very often it is not exactly specified what to do next.
We now formally define when a situation is a script.
Definition: A script S is a situation such that
(1) If the entry conditions of S are satisfied, then the entry conditions
of the first subsituation are satisfied.
(2) If the goals of the n-th subsituation are satisfied, then the
entry conditions of the n+1-st subsituation are satisfied; or in
case the n-the subsituation is the last one, if its goals are satisfied
(and those of all the previous subsituations are too), then
so are the goals of S.
(3) Each of the subsituations is itself a script.
In the restaurant situation described above, no instructions are given
for what to do if the expectation of being able to enter the next
subsituation is not met. Children learn all of the above situation and
can use it well as long as expectations are met. Knowing what to do
otherwise is extra knowledge, not a part of this situation. One could
expand this situation by providing some rules to deal with these exceptional
eventualities, and it would then still meet our definition of a script.
Thus many variants of the restaurant situation are possible, depending on
the number of exceptional situations for which rules are included.
Note that in general situations usually provide for subsituations.
It follows that the general situation really has a sort of tree structure.
At the leaves of the tree we have ``atomic'' situations that do not
involve subsituations:
Let us examine one of these in more detail.
situation : ordering the food
entry conditions: waiter(x), fellow diners(y).
In the script formalism there would be "slots" to be filled by the
waiter and the (list of) fellow diners. In our formalism filling those
slots is accomplished by unification. In order to enter this subsituation,
we have to unify the variable x with some particular person and recognize
that that person is the waiter, and the variable y has to be unified with
the list of our fellow diners (which might be empty if we are dining alone).
We expect that the situation will proceed as follows: the
waiter will stand by table within earshot, look at the diners one by one,
ask if they are ready to order (or something similar), with pencil ready
to write on his pad; the diners will order, and the waiter will leave.
This is formalized in the list of rules and goals:
rules :
if the waiter looks at you attentively;
he seems ready to write;
then desired←order(x);
tell the waiter you want x;
except if you don't know yet (i.e. desired←order(x) cannot be satisfied by unification);
then say "I need a couple of minutes more";
except if you are the last to order;
then decide←to←order (x);
tell the waiter what you want.
\footnote\dag{This simple version of the rule doesn't allow for the
case in which you need more information to decide, such as the price
of the special or whether it has a lot of garlic. This could be taken
care of by the rules for "decide←to←order".
The rules for decide←to←order(x) might require waiter(y) to
be satisfied by unification before their execution can be completed.
But the version of the rule given above would require you to wait until
everyone else had ordered before asking the waiter a question.}
goals: tell waiter order(x), waiter leaves.
Scripts are ubiquitous. Everyday life seems to consist of a
succession of scripts--at least when everything is going well.
Much of the learning that children do consists in learning
scripts. We hope that the single example given above will suffice to
demonstrate that our formalism for situations is adequate to describe
scripts; or to put it another way, that scripts as we have formally
defined them correspond to what we intuitively think of as scripts,
that is, situations in which we know how to proceed almost algorithmically
as long as things go according to our expectations.
The definition of a situation makes one of the components of a situation S
a list of rules, called the "rules of S".
The rules of S will include only those rules which are special to the
situation S. In general, every situation has not only subsituations
but, while we are in the situation, it has arisen as a subsituation of
some supersituation. The rules of the supersituations will also be
accessible to the situation. For example, in the restaurant situation we
have access to rules concerning the use of money, rules concerning
the proper distance from a person for conversation, rules concerning
the proper use of silverware, etc., which are not special to the
restaurant situation.
10. An example of a situation which is not a script
Not every situation can be sufficiently predicted that we can
organize its subsituations into the rather algorithmic form of
a script. How does this unpredictability arise? Most situations
involve "roles" to be played by other agents with whom interaction
is expected. These "slots" are to be filled by unification. In
case the possible range of actions of the other agents is sufficiently
narrow, we can specify our response in advance, as in the restaurant
situation. In that case the situation can be made into a script.
However, in many situations that will not be the case; the range of
possible actions by the other agents is too large to anticipate all
the possibilities. These situations demand a different kind of
intelligence than is demanded by a script.
A rather pure example of such a situation is game-playing, where
there is just one external agent, and at least the rules governing
the possible actions of the agent are completely known, so that
the unpredictability arises only from the large number of possibilities
permitted by the rules. It is no accident that game-playing was one
of the first areas to be investigated in AI, as it seems to be the
simplest class of non-script situations. In order to show how our
definition of situation applies, we shall start writing out the
formal definition of a chess-playing situation.
situation: playing chess
entry conditions: willing opponent, pieces, board, time, peace and quiet,
desire to play chess.
goals: to win the game.
Here we take a simplified version of the situation. For example, if the
*1*
opponent is your child or your boss or your girlfriend you may have other
goals then just winning the game.
rules: It would be too lengthy to spell them out in detail. Let it suffice
to note that they fall in two classes:
(1) the legal rules of chess
(2) general rules of strategy and tactics which are
applicable throughout the game.
subsituations: preparing to play, opening game, mid game, end game.
Now we examine the subsituations.
situation: preparing to play
entry conditions: same as those of the playing chess situation.
goals: white(x) (i.e. x will play white), board←set←up.
rules: if x played black in the previous game;
then white(x)
except if there was no previous game;
then offer the opponent the draw;
if he chooses one of your hands, say z;
then if z contains a white pawn;
then the opponent will play white;
if z contains a black pawn,
then you will play white;
except if he first offers you the draw;
then choose one of the proferred hands, call it z;
if hand z contains a white pawn;
then you will play white;
if hand z contains a black pawn;
then the opponent will play white;
"offer the opponent the draw" refers to the common procedure of holding
a pawn concealed in each hand, one of each color, and offering the opponent
the opportunity to choose one. In addition there should be rules for
setting up the board in its proper position for the start of the game.
situation: opening game
entry conditions: white(x), board←set←up.
subsituations: Giocco Peano, Sicilian, King's gambit, English opening,
Hungarian game, etc.; out←of←book.
Here we consider the subsituations to be determined by the games which are
given names in books of chess openings. There is one more possible
subsituation, out←of←book, which ensues when the play is no longer along
a book line.
goals: achieve material superiority without positional disadvantage;
maintain material equality;
develop one's pieces;
gain or compete for control of the center;
maintain the integrity of one's pawn structure;
rules: if the play so far follows a known book opening;
then find an acceptable line of play from the book, say x;
if there is no reason to reject x;
then play x;
if x is a line which resulted in a disadvantage recently;
then there is reason to reject x;
except if the reason for the disadvantage is known and remediable;
then fail (i.e. there is no reason on this account to
reject x);
In order to make the points we wish to make, it is not necessary to
write out more rules; besides, this would require more chess expertise
than the author possesses.
The chess situation may be contrasted with the restaurant situation in
one important respect: At a typical moment during the situation, there
will be in chess several active top-level goals, such as those listed
under the opening game subsituation, which require unrelated rules for
their satisfaction. On the other hand, in the restaurant situation,
the active goals will be the goals of the current subsituation, which
will automatically be satisfied if we can progress through the subsituations.
The only part of the chess situation which shares this property is the
part of the opening game in which we are playing by the book.
The point about unrelated goals can be seen in an even simpler example,
the game of tic-tac-toe. In spite of its seeming triviality, the game
is not played by brute-force search, even by computers. Instead, one
has several goals: get three←in←a←row, prevent your opponent from
getting three←in←a←row, achieve a situation in which your opponent can't
prevent you from getting three←in←a←row, prevent your opponent from
achieving such a situation. The plan for playing tic-tac-toe involves
assigning correct priorities to these goals. I have seen a three-year-old
who knew the rules of tic-tac-toe, and the goal of getting three←in←a←row,
but not the goal of preventing your opponent from getting three←in←a←row.
She was frustrated because her correct pursuit of her goal didn't win the game.
11. Planning
This section discusses the following problem: Suppose we are
given a list R of nested if-then rules, some procedures defining
the actions mentioned in R, a list of goals G, and some literals E
(the ``initial database''). The object is to come up with a plan
for achieving G from the initial condition described by E, using
the rules R.
What we mean by a plan in this context is precisely this:
a sequence of rules R1,...,Rn from the list R, together with a
sequence of proposition Ai such that
the following can be proved from R:
(1) Ai {fire(Ri)} A(i+1); that is, if Ai holds and fire(Ri) is
executed then A(i+1) will hold.
(2) E implies A1.
(3) A(n+1) implies each of the goals G.
The problem of constructing a plan is not too difficult if the actions of
external agents are not going to be involved, or if they can be
accurately predicted, or if (as in game-playing), we have rules to determine
our response, whatever the external agents do. In these cases, a
backtracking search algorithm similar to PROLOG can be used, and we
shall spell out the details of how to do that, as a preliminary
to the more difficult cases.
We have already discussed the possibility of modifying the PROLOG
interpreter to ``subjunctive mode'', in which the actions assert and
retract would be reversible on backtracking. In planning, a PROLOG-like
system should be used in subjunctive mode. We then make sure that each
possible action is defined by a PROLOG program, and then simply ask
the PROLOG interpreter to solve the goals G given the program which
defines the meaning of ``fire(Ri)'', the rules Ri themselves,
the database E#, and suitable rules expressing the effect of firing Ri.
We have already discussed the necessity for rules expressing knowledge
about the effects of firing the Ri; they are essential for planning.
\footnote\dag{As I have stated the algorithm, it will not run
in PROLOG, since it will result in trying to solve call(X) where X is
not instantiated to a particular literal; but this is a practical,
not a conceptual difficulty. We need a PROLOG interpreter modified
to accept certain second-order constructs.}
The result of this PROLOG program's execution, after backtracking is
removed, can be used to generate a plan in the formal sense defined
above.
In this simple plan-formation algorithm, rules of the form
if A and active←goal(t) then B
will not be involved in the construction of a plan, since we have made
no provision for making ``active←goal(x)'' solvable. This is all right;
such rules do not tell us what the effect of doing B will be, but only
rather vaguely that it is a good idea to do B if you want t.
Each such rule should be supplemented (by the programmer) with rules
expressing knowledge about the effects of action B; it is {\it these}
rules which will be used in forming a plan. See section 4 above for
specific examples. Perhaps a more sophisticated planning program could
make use of such rules.
We can get farther with this simple planning program than might be
initially supposed. Here is how: suppose we have a situation in
which there are indeed some external agents. We make some default
assumptions about what they will do under certain conditions. Subject
to those assumptions, we can apply the above planning program. Our
semantics of situations, which uses if-then-except rules, will be so
constructed that any deviation from the default assumptions which is
covered by one of the except-clauses, should still be handled correctly.
In the next section we will see how this works out.
In this paper, we shall not attempt a more sophisticated planning algorithm;
that is a difficult topic which is not central to our development.
12. Procedural semantics of situations.
In this section we shall define our "semantics of situations".
We shall require the concept of the ``default version'' of a rule,
which has been defined above.
Another preliminary definition is also required.
If S is a situation with entry conditions E and goals G,
then we define abs(S) to be the clauses expressing
if E then G. More precisely, if E=E1,...,En, and G=G1,...,Gm,
then abs(S) is the list of m clauses
if E1,...,En then Gi
The terminology "abs (S)" is arbitrary, but suggests that
replacing S by these clauses represents an abstraction that
achieving goal G under conditions E is something that we
know how to attempt (using S), and assuming everything goes
well, we can do; so using abs(S) instead of S, we ignore the
details of how to achieve S.
We want to define for each situation S an algorithm do(S),
such that the meaning of S is "execute do(S)". Since we want
subsituations to inherit the rules and goals of their supersituations,
it turns out to be more convenient to define do(S,R,G), where
S is a situation, R is a list of if-then-except rules, and G is a list
of goals. We will then define do(S) to be do(S,R,G), where R is the
list of rules of S, and G is the list of goals of S. Moreover, the
algorithm do(S) will also depend on
the particular unification that has taken place to satisfy the entry
conditions of S; that is, we shall never attempt to execute do(S)
unless a unification has taken place such that some instances
E# of the entry conditions E of S are satisfied. We therefore
have to define not only do(S,R,G), but do(S,R,G,E#), where E# is any
instance of E obtained by a unification.
Suppose S has entry conditions E, rules R=R1,...,Rm,
subsituations A1,...,An, and goals G. We form a list of if-then rules,
try(S,R), whose members are
(1) R sub D, the default version of the list R, followed by
(2) abs(A1),...,abs(An).
The first step in do(S,R,G,E#) calls for giving the program
try(S,R) and the database E#, with the list G of active goals,
to the plan-generating program discussed in the previous section.
The result, in the event this step is successful, is a plan,
for what to do in situation S under the conditions E#.
More precisely, it is a sequence of rules from try(S,R),E#, say
R1 sub D,...,Rn sub D, and intermediate conditions Ai,
such that firing these rules in that order can be proved (from the
program try(S,R),E#) to achieve goals G; and the intermediate results
that Ai is true after the firing of Ri sub D in sequence can also
be proved.
We therefore refer to the program try(S,R), E# as the "planning program".
The creation of a plan from try(S,R),E# is the first stage in the
execution of a situation. Note that in case the situation is a
script, the planning program will naturally produce the obvious
plan: to execute the subsituations one by one in the same order
they are listed. In the case of a more complicated situation, it
may be more difficult to come up with a plan. The plan represents
a proposed course of action, which will work if all default assumptions
are valid, including the default assumptions that every subsituation
which is entered can be successfully exited.
We next carry out the plan, as follows.
We go through the planned sequence of rules R1,...,Rn and the
corresponding proof produced by the planning program in
order. When one of the Ri sub D is to be applied,
{\it we fire the rule Ri}, not the rule Ri sub D.
Then we check that the corresponding postcondition is really satisfied.
If either the postcondition, or the execution itself, fails, then
something has gone wrong. We shall postpone for a moment the instructions
that apply in this case; so let us assume that nothing goes wrong.
When one of the clauses abs(Ai) is called,
we replace that application by an execution of do(Ai,R,G,B#),
where B# is the current instantiation of the entry conditions of Ai.
We first check that B# is really satisfied; if not, something has gone
wrong. If do(Ai,R,G,B#) terminates successfully
(that means that it terminates, and when it does so, the goals of
Ai are satisfied), then we continue going through the proof.
If we successfully finish going through the proof, and when we finish,
the goals G of S are satisfied, then do(R,S,E#) terminates successfully.
Now we have to tell what to do in case something goes wrong. One of the
important features of our definition is that we have smoothly taken care
of most of the ways in which things can go wrong, at least those which
we know how to take care of at all, by using the full if-then-except rule
Ri instead of Ri sub D. For example, if the goal is to get into
Luigi's restaurant, and the plan is to go through the front door,
a little glitch like finding the front door locked is no problem;
firing Ri instead of Ri sub D will cause us to check if the door is
locked when the routine go←through(Luigi's,front←door) fails, and then
to fire the rule which tells us to look inside for people or signs of
activity, and if we see them to locate another door and go through it.
As long as the except-parts of the rules enable us to recover our
position enough that the postconditions mentioned in the plan are still
satisfied, nothing serious will go wrong. This example is worked out in
detail below.
That said, there are still several ways in which something can go wrong:
(1) One of the rules Ri doesn't work.
(2) One of the do(R,Ai,B#) terminates unsuccessfully.
(3) One of the propositions Ai fails.
There is also the possibility that one of the do(R,Ai,B#) fails to
terminate at all; but in that case do(R,S,E#) also fails to terminate;
no remedy is provided.
When these cases occur, the fault may well lie in our ignoring the
except-parts of the rules Ri in the correctness proof of the plan,
rather than in the rules which are to be fired. So in these cases,
we go back to the beginning of the proof,
and start over. This time, each time a rule Ri sub D is applied (that
is, when PROLOG solves fire(Ri sub D)), we
check the except-if part of the rule Ri. Say that Ri is
if A then B except (if C then D except F). By the time this is applied
in the proof, some substitutions may have been made for variables,
so the actual rule applied is
if A@ then B@ except (if C@ then D@ except F@) for some
substitution @.
Then we check whether C@ is satisfied. If it is not, we proceed.
If it is, however, we then have firm evidence that the original
plan was faulty, since the default assumptions embodied in it were
not satisfied. In that case, we should add the rule
(if C@ then D@ except if F@) to R, and we should
modify the original rule by adding not(equal(x,x@)) to the hypothesis
of Ri. Let us call this modified list of rules R2. By the time we
noticed that something had gone wrong, we might have changed the
original conditions E# irrevocably by our actions; so let E2 be the
current database. We then execute do(S,R2,G,E2).
If, however, we make it through the whole proof and do not find a
rule Ri whose except-if part is satisfied, then our original plan
was faulty for unknown reasons. We therefore reject it, and return
to the program which produced it, and ask for another solution.
Another solution, that is, not to the original problem, but to the
present situation, as modified by our actions to date, as discussed
in the last paragraph. If that program can produce another solution,
we proceed with this new plan as before.
The definition is recursive. The first recursion theorem guarantees
the existence of a least solution to the recursion equations defining
the algorithm ``do''. Whether or not it produces output when given
a particular situation as input, we cannot say.
\footnote\dag{We have managed to keep things simple by not explicitly
introducing the element of time. In everyday life, of course, if the
algorithm do(S,R,G,E) does not terminate in a reasonable time, there
is a default recourse: yell ``help!''.}
Let us look at some examples in more detail. Consider first a
simple example in which there are no subsituations. Let S be the
situation, entering a building. The entry conditions express
that we are outside a building and want to be inside.
E is building(x), outside(x), active←goal(inside(x)).
The rules R include the rule R1:(which have been expressed less formally
in section $ above)
if outside(x);
active←goal(inside(x));
door(x,y);
then go←through(x,y);
except if locked(y);
then look←inside(x);
see←people←or←signs←of←activity;
locate←door(x,z);
not(z=x);
go←through(x,z).
Here locate←door is a compound action (list of actions) such that
specifying how to locate a door y in building x;
these may be thought of as rules with conclusion door(x,y).
We think of door(x,y) as meaning we are standing in front of the
door y in building x. There should also be rules for performing
the other actions mentioned in R1; but these rules would not be
part of situation S, since the activities
are more general, but would be inherited from the supersituation.
Let Q be a list of rules including R and all the rules for performing
actions mentioned in R1. The goal G is inside(x). We are interested
in do(S,Q,G,E#). Let us suppose we are standing in front of Luigi's
restaurant. Then E# is
building(Luigi's), outside(Luigi's), active←goal(inside(Luigi's)).
The default version of R1 is
if outside(B);
active←goal(inside(B));
door(B,y);
then go←through(B,y).
This represents the default assumption that doors can be gone through.
The planning program consists of this clause, plus "outside(Luigi's)",
plus the default versions of the other rules in Q. One of the rules in Q
will be
if outside(x),door(x,y),go←through(x,y);
then inside(x).
When we try to satisfy the goal "inside(Luigi's)", the planning program
will use this rule to try to satisfy
outside(Luigi's), door(Luigi's,y), go←through(Luigi's,y).
Since "outside(Luigi's)" is part of the database, it is satisfied.
The program then tries to satisfy "door(Luigi's,y)". To do that, it
uses a rule in Q of the form (written in PROLOG)
door(x,y):-locate←door(x,y).
which says, to be in front of a door y in x, execute the procedure
locate←door(x,y). It will then run the procedure locate←door(Luigi's,y),
which let us say results in finding the front←door of Luigi's. We
then have door(Luigi's, front←door). Now we try to satisfy
"go←through(Luigi's, front←door)". We make use of the default version
of R1 for this purpose, which says that it would suffice to satisfy
"outside(Luigi's), active←goal(inside(Luigi's)), door(Luigi's,y)." Now
"outside(Luigi's), active←goal(inside(Luigi's))" is already satisfied, and
unifying y with front←door, we have all the necessary clauses satisfied,
and success is reported. A plan has been found: to get into
Luigi's, we should go through the front door.
Now we try to execute the plan according to do(Q,S,E#). But to our
chagrin, when we try to execute go←through(front←door), we fail. That
is, when we come to apply the rule,
go←through(x,y):-outside(x),door(x,y),want←to←be←inside(x).
we find that the conclusion go←through(front←door) fails even though
the hypotheses hold. The definition of do(Q,S,E#) requires us in
this case to examine the except-if part of the rule R1, namely
except if locked(y)
Now we check whether locked(front←door). Sure enough, the front door
of Luigi's is locked! Then the definition of do(Q,S,E#) requires us
to fire the following:
look←inside(Luigi's);
see←people←or←signs←of←activity;
locate←door(Luigi's,z);
not(z=front←door);
go←through(z).
and to modify the original rule to
go←through(y):- outside(x,y),door(x,y),want←to←be←inside(x),
not(y=front←door,x=Luigi's).
Suppose that when we look inside, we do see people or signs of activity.
Then locate←door is called, and after the next literal fails with
z=front←door, locate←door is called again. Say it produces z=side←door.
Then we execute go←through(side←door). Now the definition of
do(Q,S,E#) has us return to the plan at the point where R1 should have
left us. That happens to have been the end of the plan, where we should
have been inside Luigi's. So we check whether we are inside Luigi's,
and indeed R2 can be used to deduce inside(Luigi's). Hence the goal
of S is satisfied, and the execution of do(Q,S,E#) has terminated
successfully.
Note that we did not have to stop to make another plan. We just followed
the instructions embodied in the except-parts of the rules.
13. Example: the blocks world.
The "blocks world" is a table with some blocks on it. Let us suppose
that all the blocks are cubical, but they may be of different sizes.
Every block has a color (and exactly one color), and perhaps other
properties as well. We write on(x,y) to mean that block x is immediately
on top of block y. Let us suppose that this is only possible
if block x does not overlap the edges of block y; in particular
a big block cannot be placed on top of a little block.
A typical rule available in all blocks-world situations might be:
if x is not bigger than y;
then x can be put on top of y;
except if on(z,x) (i.e. something is already on x);
then z can be moved off x;
if on(w,y);
then if there is still room on top of y for x;
then x can be put on top of y (after all);
if there is not enough room on top of y for x;
then you can move w off y;
This last part is a very crude rule; it might be better to move
off the largest block and check again whether there is room for x,
recursively; or to somehow estimate how many or which blocks should
be removed. But these refinements are beside the point, which is only
to illustrate the type of rules to be considered.
The simple planning program described above should work very well
to generate plans for achieving specified configurations of blocks
under given conditions. Consider, for example, the problem of
getting a red block on top of a green one. When some initial conditions
are specified, a plan will be generated. In the course of executing
that plan, something may well go wrong; for example, the plan may call
for moving a block that has something on top of it (if the information
about the existence of the block on top was omitted at first).
But the procedural semantics of situations will then call into play
the except-part of the rule above, resulting in moving the obstructing
block off, after which the execution of the plan can continue.
The blocks world would no doubt be a nice test run, should the
formalism described in this paper ever be implemented as a computer
program. In situations of moderate complexity it would perhaps
outperform a human. When one is ready to experiment with external
agents, they may be given the ability to move blocks or paint them.
14. Another example: travelling
The formalism described above controls reasoning and action in what
seems to the author a very natural fashion. Here is the essence of
our formal definitions, summarized in everyday language:
We first formulate an overall plan, based on some default assumptions.
We then try to carry out the plan. At each of its major stages, we
stop to formulate a more detailed plan. We then try to carry out that
plan, and so on, recursively. If ever a planned action doesn't work,
or doesn't produce the desired result, we check whether we know what to
do in that case (by checking the except-parts which we ignored in
formulating the plan). If so we are perhaps able to recover from
the setback and continue more or less as planned. If not, we have
to stop and re-think the situation.
The author believes that the power of this definition will only become
really evident in situations of moderate complexity, where the
behavior of the formalism could only be modelled by a computer
program. In this paper it has been possible to include only the
very simplest examples, which no doubt could be handled by simpler
means.
One example which is too long to work out in detail, but on which a
computer program should certainly be tried, is the much-discussed
problem of travelling from point A to point B.
\footnote\dag{Newell, Shaw, and Simon first considered the problem
as an illustration of their GPS program. The only knowledge about
the effects of trips they included was the effect on the distance
remaining to travel. The control structure of GPS consists in:
reduce the distance to the goal.}
For example, from my house in Aptos, California, to my friend's
house in Utrecht, The Netherlands.
We would of course begin by writing down a number of rules about how
you can travel: by car, by taxi, by bus, by train, by airplane, walking,
and so on; the rules give certain conditions under which it is
appropriate to use a car, a plane, etc. As we have emphasized above,
it will also be necessary to include some knowledge about the effects
of trips.
I will now present the process of going from Aptos to Utrecht in
such a way that it could represent either a human process, or an
execution of a program based on the formalism of this paper.
Suppose my goal is to travel as described on or about May 15, 1985,
alone but with several suitcases, subject to the constraints that the
journey take at most two days and be as cheap as possible subject to
the time constraints. The first observation about the travel problem
is this: nobody (except GPS) sets out to travel from Aptos to Utrecht
without a plan. One first realizes that a plane trip will be necessary.
(Only a plane or ship can cross the ocean, which I know lies between
Aptos and Utrecht; and a ship is too slow.) To take a plane trip, I
will need a ticket and reservation; these are obtained in advance through
a travel agent; so the planning program calls the travel agent (in
subjunctive mode!). The default assumption is that a reservation can
be obtained on the desired day. Then the rest of the plans are made:
I will take a bus to the airport (since taking my car necessitates leaving it
at the airport, which fails to satisfy the secondary constraint goal
that I get there the cheapest way that still meets the time constraint).
I will have to get a friend to take me to the bus. At the other
end, I will take either a bus or a train to Utrecht, and then a taxi
to my friend's house. (Here my human plan exceeds the capabilities
of the simple planning program described in the text; I propose a
variation in the plan, and a condition to be checked at the time
of execution: if the railroad now runs to the Schiphol airport,
where I will land, I will take a train, and otherwise a bus. When
I last was there, the railroad was under construction. The program
will just choose the first plan that meets the goals.)
There are several rules in the travel situation that apply if the
starting point and destination are in different countries. For
example, in that case you must have a passport and you must go through
customs when entering the destination country. These rules will
result in the plan including a step for going through customs at
Schiphol, and a plan to make sure that I have a passport before the trip.
Now we go to execute the plan. The first step is to solve
the predicate travel←agency(x). I have a rule that says
I should choose Santa Cruz Travel (I added that rule to my program
after using their services successfully before).
Now I enter the subsituation, use←travel←agency, since the plan
calls for getting a ticket and reservation using a rule
abs(use←travel←agency) representing the default assumption that
tickets and reservations can be obtained from a travel agency.
That subsituation contains three subsituations: get←information,
make←reservation, and get←ticket. I now have to make a local plan
for going through the situation use←travel←agency. It is simple
enough: I'll call them up, make a reservation, and get the ticket.
So I call them. The first step is get←number(Santa←Cruz←Travel,x);
I try to look it up in the phone book. But I can't find the phone
book; God only knows where it has disappeared to, and the action
look←up(Santa←Cruz←Travel,x) fails.
No problem; I check the except-part of the rule for get←number and
it says if you can't look it up, call 411. I call 411 and get the
number. But the line turns out to be busy. No problem; I
check the except-part of the rule for making a phone call and find
that it says if the line is busy, try again in a few minutes.
So I try again in a few minutes, and get through to the travel
agent this time. Under the control of one of the rules in the
use←travel←agency situation, I ask the person who answers for an
agent who can make a plane reservation. She connects me to one,
and I then enter the make←a←reservation subsituation. Let us suppose
all goes well there, and I succeed to make the resevation. I then
enter the get←ticket situation. Here I have a special rule that
applies if the travel agency is Santa Cruz Travel: tell them that
they have some American Express forms of mine in the safe and can
therefore mail the tickets, so that I don't have to go in to pick
them up. Sure enough, this rule succeeds, and the tickets come
in the mail. I exit from use←travel←agency.
Next the plan requires me to get a valid passport, i.e. to
solve valid←passport(I,x). As this procedure requires, I check
whether mine will still be valid for the duration of the planned
trip. It turns out to be still valid, so I exit valid←passport
successfully.
\footnote\dag{However, I waited for the tickets to arrive from the
travel agency before checking my passport. This was silly; I could
have checked it any time. To get the computer to do that, however,
will have to await parallel processing, or some substitute such as
putting the use←travel←agency situation in the ``background'' while
awaiting an action on the part of an external agent.}
The oversimplified version of the situation we are considering says
nothing about packing for the trip, so we neglect that. The next
step in the overall plan is to get a friend to take me to the airport.
This part of the plan is based on some rules inherited from
supersituations; in particular, on general facts about what kind of
favors friends can be expected to perform. The choice of which friend
to ask to do this job will depend on a fairly intricate collection of
rules. Let us suppose, however, that all goes well, and on the
morning of May 15, we enter the situation ride←in←car with the goal
of getting to the bus station by 10 a.m. What if something goes
wrong? Let's say the car has a flat tire. Then the except-parts
of certain rules come into play, and they say that if there is
mechanical difficulty which can't be immediately fixed, then if
I am in a hurry I should find some other means of transport.
\footnote\dag{Note that it would be a programming error to have
written the rule in the form, you should stay and help fix the
trouble except if it takes too long. The condition on it taking
too long cannot be in the except-part, since it won't then be
checked in time.}
So I check my rules for finding means of transport, and conclude
that I had better call a taxi.
\footnote\dag{Here the program is weaker than
the human: the program has no way to recognize that it is in a
new situation, namely that of without←transport←in←public, and
call on the procedural semantics of that situation. If the rules
alone for finding←transport are not sufficient, we are in trouble.
This capacity for recognizing what situation we are in is an
important one, which should be built in eventually.}
After some difficulties, I find a phone, call a taxi, and it comes
and takes me to the bus station. I enter the ride←the←bus situation.
This is a script, and I follow it successfully, arriving at the
airport, where I follow the catch←departing←flight script. This
script has several subscripts, including check←baggage,go←to←gate.
During my execution of go←to←gate, I enter the subscript,
airport←security←check. I form the plan to wait my turn, identify
the guard (i.e. solve guard(x)), put my briefcase on the conveyer belt,
walk through, see no opposition from the guard, pick up my briefcase,
and exit the situation. As it turns out the bell rings and the
guard does oppose my passage. I then check the except-part of the
rule for see←no←opposition, and it says to do what the guard requests.
That happens to be to take any metal out of my pocket, give it to him,
and try again to walk through the security gate. I find some keys in
my pocket, give them to him, and try walk←through again. This time
it succeeds.
I arrive at the gate and enter the subsituation, board←aircraft.
This is another script; I follow it and wind up on the airplane.
My activities during the trip are controlled by the ``ride←airline''
situation; this situation terminates when I leave the airplane at
Schiphol airport. The plan calls for me to pick up my checked baggage,
go through customs, take the train to Utrecht, and take a taxi to my
friend's house.
The example so far illustrates the way the formalism works in case what
goes wrong is an action. It does not, however, illustrate the more
drastic troubles that arise when one of the propositions Ai fails
to be true as expected, but one doesn't notice it until later.
For example, suppose the proposition
if I check my baggage at the airport;
then it will be put on the plane with me.
turns out to be false. I will run into trouble when I can't get through
the pick←up←checked←baggage situation at Schiphol. After checking
all my except-clauses, I still can't find my bags, which is necessary
to exit the situation successfully. At that point I will check over
the proof of correctness of the overall plan, and doubt will be cast
on the proposition mentioned. I must then re-plan how to get to
Utrecht with my luggage from the present condition. The first thing
to be achieved is to solve luggage(x). Where is my luggage anyway?
I have general rules for finding lost items; one of them is to ask
the agent who had it last. That was the airline. So I plan to
inquire about the lost bags, recover them, and take the train to
Utrecht. This plan makes the default assumption that recovering
the bags will succeed. I proceed to execute it. The airline promises
to find the bags and deliver them to my friend's house. Nothing in
the goals of the travel situation says that my baggage and I have to
arrive together; the goal only says that we both have to arrive.
The present version of the formalism would require me to sit in
limbo at the airport until the procedure for recovering bags
succeeded; for the sake of a successful example, let us suppose the
airline finds my bags rather quickly and returns them to me.
In the next section the general problem of timing will
be discussed. A future version would form a new plan when informed
that waiting for the bags will take too long, and proceed independently
to Utrecht under the control of that new plan.
15. What the formalism of this paper can't do (yet)
The purpose of this section is twofold: to give an idea of the
limitations of the formalism presented above, and to give an idea
of some possible extensions of the formalism.
Suppose, in the travel example above, that my passport had been
expired, so that I am required to solve valid←passport(I,x) some
other way than just by checking my current passport. I may well
have formed the plan on the basis of a clause like,
if US←citizen(x)
then can(x,get(valid←passport(x,y)))
together with the knowledge that I am a US←citizen.
The simple version of the planning program discussed above would not
permit this, but a slight modification of it would, and in general
it is a useful thing to know that an action {\it can} be performed
without knowing exactly how. But now it turns out that I need
to know how. That is, I need to acquire new knowledge; I need to
expand and modify my program; I need to learn.
In the example at hand, I recognize that the knowledge needed is
how to obtain document x from the government; and I have been
in the situation before, of needing to know how to get document x
from the government. I have some rules for how to proceed to acquire
that knowledge. I shall not pursue the example further; the point is
that learning, at least some kinds of learning, can be described in
terms of situations, and rules for learning can be given in the same
formalism.
It is connected with the problem of modelling other ``minds'', or
more neutrally, other agents, since one important way to learn is
by watching the behavior of others.
In order to cope with ``everyday life'', one needs some notions about
time. A formalization of time is the next thing that needs to be
added to the formalism. An example of where such a formalism is
needed is in the ability to judge when a procedure is taking too long
to execute and should be aborted. A more important example is the
need to remember what happened on previous occasions when we were in
the same situation we are in now. Next one should add principles about
causality, as McCarthy suggested twenty years ago in [1963].
With time and causality formalized, we will be in a position to
write, in the formalism of situations, a more sophisticated control
structure for the improvement of one's own programs. For example,
in the travel scenario above, my program contained a rule for finding
a travel agency, namely to call a particular one. I added that rule
to my program after a successful experience of the use←travel←agent
situation with that unifying substitution. That's a simple rule: if
a certain unifier worked last time, use it again, except if there's
a reason not to.
Another direction in which the present formalism is limited is in the
flexibility of the planning program. We have already seen that the
program as given would not be able to generate the plan to go from
Schiphol to Utrecht by train, if the train is now running, or else
to go by bus as before. That is so even if it had the general rule
that if one can go either by bus or by train, one should go by train.
A more sophisticated program would be able to make more use of the
construct can(A), where A is an action, together with rules about
preferences. In general preferences are not absolute, as in the
example where I always prefer trains to buses; so the planning problem
impinges on the inexact-reasoning problem. Our positive suggestion
here is to use the procedural semantics of situations as a bootstrap:
write a planning program using the formalism presented in this
paper, then use that planning program in place of the simple one
given here to improve the formalism.
Date: 23 May 85 1059 PDT
From: Vladimir Lifschitz <ucbvax!VAL@SU-AI.ARPA>
Subject: Logic and Knowledge
To: beeson@ucscd.ucscc.UUCP
I just finished reading your very interesting paper. I'm afraid I couldn't
quite appreciate some of the details because of my insufficient understanding
of PROLOG. Here are some questions and remarks.
1. It seems that a basic idea of McCarthy's approach to knowledge representation is
that knowledge should be represented in a form not related to any particular way of
using it (at least, in most cases). His favorite example is: "There is usually
a noise when things collide". You can use this fact to make noise, or to avoid
noise, or to explain noise, but in each case you use the same commonsense fact.
What is your attitude towards that? It appears that your formalism rejects this
idea from the very beginning. Maybe you should comment on that in the paper.
2. Your analysis of default reasoning in Sec. 1 differs in one respect from
what seems to be the usual understanding. Usually we assume by default that
the contraindications do not apply unless we know that their preconditions are
satisfied. That is, when we want to decide whether the bird Tweety can fly,
we check whether any information is available that would imply C1, C2,... .
If not, we conclude that it can. From this point of view, default reasoning
is reasoning with incomplete information. This differs from your approach:
we look at C1, C2,... when trying to apply the rule and do not wait until
"something goes wrong". This is apparently the way default reasoning is understood
in Reiter's default logic, in closed-world data bases, in predicate completion
and in circumscription. What is the relationship between this understanding and
yours.
3. The description of reasoning in "subjunctive mode" in Section 5 reminded me the
distinction between "operators" and "action routines", made very clear in the
paper about the STRIPS planning system by Fikes and Nilsson in AI Journal 2(1971),
189-208. They say: "Operators are the basic elements from which a solution is
built. For robot problems, each operator corresponds to an action routine whose
execution causes a robot to take certain actions." And then in a footnote:
"The reader should keep in mind the distinction between an operator and its
associated action routine. Execution of action routines actually causes the robot
to take actions. Application of operators to world models occurs during the
planning (i.e., problem solving) phase when an attempt is being made to find a
sequence of operators whose associated action routines will produce a desired
state of the world".
4. In the first example in Sec. 12, z=x should be apparently z=y.
5. I don't quite understand your use of "can" in the example of Sec. 13. It
looks as if you were giving a rule for determining what we are physically able
to do with the blocks. You don't use "can" in other examples. Is there any reason
for that?
- Vladimir
And now here is my reply
Thanks for your helpful comments and for the reference, of which I was
unaware. I was aware that waiting until something goes wrong to check
the default conditions is not the way people view default reasoning,
but I think it is a useful innovation. Sometimes it is not correct,
however, as in the following rule for driving on a freeway:
if on a freeway
then drive at whatever speed you consider safe and expedient
except if you see a policeman
then drive 55
except if the policemean's car is stopped
and he is busy with another motorist
then drive at whatever speed you consider safe and expedient.
You better not wait until something goes wrong to check for policemen!
Thus my semantics does not correspond in every situation to the natural
one. But in many it does, and as a programming language for AI it can
be made to do. In general the exceptional conditions are of two kinds,
those that have to be checked before the action, and those that should not
be checked until something goes wrong.
A more sophisticated version of my system would include an explicit
representation of time, or at least the sequence of events, together with
parallel execution of situations and the ability of one procedure to
interrupt another. Once this is done, I will be able to distinguish the
above kinds of exceptions better. In the current system, it is the
programmer's job to put the kind that have to be checked first in the
if-part, instead of in the except-part. See the footnote in the
travel example for one example of this.
As to your point about using the same knowledge different ways,
I think my system does that fine. The example you give,
if collides(x,y)
then noise
except if you are too far away
or x and y are in a vacuum
is a very general rule and would belong to the collection of
rules shared by many specific situations. That is, in all the
situations I considered as examples, it would be a rule inherited from
the supersituation. Thus in one situation, that rule might be used
to avoid noises, and in another situation it might be used to
create noises.
In the next draft of the paper, I shall certainly bring this point
out better to avoid creating the misimpression you received.